#include <stdio.h>
// 直插排序
int insert_sort(int dat[],int len){
    int i,j;
    // 从dat[2]~dat[n] 依次插入到前面已经排好序的序列中
    for (i = 2; i <len ; ++i){
        // j作为游标，从当前位置依次往前比较
        j=i-1;
        // dat[0] 储存当前待插入的元素（也作游标，防止游标越界）
        dat[0] = dat[i];
        // 从待插入元素的前一个往前比较比，
        while(dat[0]<dat[j]) {
            dat[j+1] = dat[j];//比它小则向后移动
            j--;
        }
        dat[j+1] = dat[0]; //插入
    }
    return 1;
}
// 折半查找
int binary_search(int dat[],int len,int key){
    int low=1,hight = len-1,mid;
    while(low<=hight) {
        mid = (low+hight)/2;
        if(dat[mid]==key)
            return mid;
        else if(dat[mid]>key)
            hight = mid-1;
        else if(dat[mid]<key)
            low = mid+1;
    }
    return -1;
}
// 折半插入排序
int insert_sort2(int dat[],int len){
    int i,j;
    int mid,low,hight;
    for (i = 2; i < len; ++i){
        low = 1;
        hight = i-1;
        dat[0] = dat[i];
        // 折半查找 寻找插入位置
        while(low<=hight) {
            mid = (low+hight)/2;
            if(dat[mid]>dat[0])
                hight = mid - 1;
            else
                low = mid + 1;
        }
        // 找到插入位置 hight+1 移动之后的元素
        for(j=i-1; j >= hight+1; j--){
            dat[j+1]=dat[j];
        }
        dat[hight+1] = dat[0]; // 插入
    }
    return 1;
}
int shell_sort(int dat[],int len){
    int i,j,dk;
    for (dk = len/2; dk >= 1 ;dk =dk/2){
        // 内部与直插排序
        for (i = dk+1; i <= len; ++i){
            j = i-dk;dat[0] = dat[i];
            while(j>0 && dat[0]<dat[j] ) {
                dat[j+dk] = dat[j];
                j = j-dk;
            }
            dat[j+dk] = dat[0];
        }
    }
    return 1;
}
int main(void){
    int a[11] = {0,99,158,1,17,23,6,7,75,34,657};

    // insert_sort(a,10);
    // insert_sort2(a,10);
    shell_sort(a,10);
    for (int i = 1; i < 11; ++i)
        printf("%d ",a[i] );
    printf("\n%d ",binary_search(a,10,7));
    return 0;
}